class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //sort之后第一个数<=顺序，第一个数相等时第二个数降序排列，当选择第二个数增序列时，第一个数相同的几组最多只会有一个进入，这时第一个数也是增序，nb的算法、
        //pair数据的最长严格递增子序列
        sort(envelopes.begin(),envelopes.end(),[&envelopes](const vector<int>& a,const vector<int>& b)
        {
            return a[0]!=b[0]?a[0]<b[0]:a[1]>b[1];
        });
        int n=envelopes.size();
        vector<int> dp;
        dp.push_back(envelopes[0][1]);
        for(int i=1;i<n;i++)
        {
            if(envelopes[i][1]>dp.back())
            {
                dp.push_back(envelopes[i][1]);
            }
            else//把envelops[i][1]放到第一个小于envelops[i][1]后面去更新dp表   1，2，10，12    7
            {//那就是找第一个大于等于envelops[i][1]的数
                 int left=0,right=dp.size()-1;
                 while(left<right)
                 {
                    int mid=(left+right)/2;
                    if(dp[mid]<envelopes[i][1])
                    {
                        left=mid+1;
                    }
                    else
                    {
                        right=mid;
                    }
                 }
                 dp[left]=envelopes[i][1];
                
            }
        }
        return dp.size();

    }
};